class MinHeap {
  constructor() {
    this.heap = [];
  }
  size() {
    return this.heap.length;
  }

  peek() {
    if (this.size()) {
      return this.heap[0];
    }
    return null;
  }
  /* 
  添加的时候,向后面添加,向上面移动

*/
  push(node) {
    this.heap.push(node);
    // 将node传入主要是为了后面继承的改写罢了,万一node是一个对象呢?我们只需要使用node节点的某一个字段进行比较,抽出compare函数也是一样的道理,后面继承的时候直接改写compare函数就可以了
    this.shiftUp(node, this.size() - 1);
  }

  /* 
    删除节点
    使用最后一个节点替换掉第一个节点,然后向下移动
  */
  pop() {
    if (!this.size()) {
      return null;
    }
    if (this.size() === 1) {
      return this.heap.pop();
    }
    let lastNode = this.heap.pop();
    this.heap[0] = lastNode;
    this.shiftDown(this.heap[0], 0);
  }
  // 比较函数
  compare(a, b) {
    return a - b < 0;
  }
  // 变量交换
  swap(idx, parentIdx) {
    [this.heap[parentIdx], this.heap[idx]] = [
      this.heap[idx],
      this.heap[parentIdx],
    ];
  }
  // 向上移动
  shiftUp(node, idx) {
    let parentIdx = (idx - 1) >> 1;
    while (idx > 0) {
      if (this.compare(node, this.heap[parentIdx])) {
        this.swap(idx, parentIdx);
        idx = parentIdx;
        parentIdx = (idx - 1) >> 1;
      } else {
        break;
      }
    }
  }
  // 向下移动
  shiftDown(node, idx) {
    while (idx < this.size() - 1) {
      let leftIdx = (idx + 1) * 2 - 1;
      let rightIdx = leftIdx + 1;
      // 左子节点肯定有,右子节点未必有
      if (this.compare(this.heap[leftIdx], node)) {
        // 左子节点小于父节点
        if(typeof this.heap[rightIdx] !== 'undefined' && this.compare(this.heap[rightIdx], this.heap[leftIdx])){
          // 右子节点存在并且小于左子节点
          this.swap(rightIdx, idx);
          idx = rightIdx;
        }else {
          this.swap(leftIdx, idx);
          idx = leftIdx;
        }
      } else if (typeof this.heap[rightIdx] !== 'undefined' && this.compare(this.heap[rightIdx], node)){
          // 右子节点存在并且小于父节点
          this.swap(rightIdx, idx);
          idx = rightIdx;
      }else {
        break
      }
    }    
    
  }
}